package leetcode;

/**
 * 42. Trapping Rain Water
 * 
 * @author zhujb
 *
 *         2017年9月4日
 */
public class leet042 {

	/**
	 * For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 0 1 3 7 8
	 * 
	 * @param height
	 * @return
	 */
	public int trap(int[] height) {

		if (height.length <= 2) {
			return 0;
		}

		int result = 0;

		int start = 0;
		int end = height.length - 1;

		L: while (start != end && Math.abs(start - end) != 1) {
			System.out.println("start:" + start + " value:" + height[start] + "end:" + end + "value:" + height[end]);
			int t = 0;

			if (height[start] <= height[end]) {

				/**
				 * 从小到大,移动左端
				 */
				for (int i = start + 1; i <= end; i++) {

					if (height[start] > height[i]) {
						t += height[start] - height[i];
					} else {
						start = i;
						result += t;
						continue L;
					}

				}
			} else {
				/**
				 * 从大到小, end为
				 */
				for (int i = end - 1; i >= start; i--) {

					if (height[end] > height[i]) {
						t += height[end] - height[i];
					} else {
						end = i;
						result += t;
						continue L;
					}

				}
			}

		}

		return result;
	}

	/**
	 * For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 0 1 3 7 8
	 * 
	 * @param height
	 * @return
	 */
	public int trap2(int[] height) {

		int i = 0, j = height.length - 1, result = 0, plank = 0;
		while (i <= j) {
			// 从零开始只会增加
			plank = plank < Math.min(height[i], height[j]) ? Math.min(height[i], height[j]) : plank;
			// 从低的那边开始算
			result = height[i] >= height[j] ? result + (plank - height[j--]) : result + (plank - height[i++]);
		}
		return result;

	}

	public static void main(String[] args) {
		leet042 leet42 = new leet042();

		int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
		// int[] height = { 2,0,2 };
		System.out.println(leet42.trap(height));
		System.out.println(leet42.trap2(height));
	}

}
